package exercise;

// 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
// https://leetcode.cn/problems/permutations/

import java.util.ArrayList;
import java.util.List;

public class L230630_I {
    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        boolean[] used = new boolean[len];
        List<Integer> path = new ArrayList<>();

        dfs(nums, len, ans, used, path, 0);
        return ans;
    }

    /**
     * @param nums  原数组
     * @param len   原数组的长度
     * @param ans   存放最终的答案
     * @param used  这个数是否被 path 使用过
     * @param path  临时存放并且符合条件的单个答案
     * @param depth 这个数组的深度
     */
    private void dfs(int[] nums, int len, List<List<Integer>> ans, boolean[] used, List<Integer> path, int depth) {
        if (depth == len) {
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                path.add(nums[i]);

                dfs(nums, len, ans, used, path, depth + 1);

                // 回溯
                path.remove(path.size()-1);
                used[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        L230630_I solution = new L230630_I();
        List<List<Integer>> lists = solution.permute(nums);
        System.out.println(lists);
    }
}

